A public repository of some of the materials of the CISC320 Spring 2021 AlgoTutorBot Adventure
This project is maintained by acbart
Hello students, thank you for agreeing to help me recapture Dr. Bart. I am sure that with your coding prowess, and
my AlgoDeathBots
, we will have no trouble finding him efficiently. My strategy is simple, you just have to:
Some details you must follow:
O(RV + RE)
time, where R
is the number of robots, V
is the number of rooms, and E
is the number of connections.Problem: Find the last visited node in a traversal and calculate shortest path to it from certain other nodes.
Input: The filename of a local file containing a sequence of rooms and their neighbors, each on their own line. The first line contains the number of rooms in the house, and is not included in the number of vertices. You can assume that each line will contain only one room’s information. The lines are ordered alphabetically by the name of the room. The neighbors within a line are also ordered alphabetically.
A room’s information consists of the following information, separated by spaces:
name
of the room, without spaces and no more than 256 characters long.robot
or empty
to indicate whether that room has an AlgoDeathBot in it.neighbor
rooms, still separated by spaces.So each line contains at least 3 space-separated substrings, possibly more. All room links are provided bidirectionally - if room A has an edge to room B, then room B has an edge back to room A.
An example of several records are below:
4
Kitchen empty Office Parlor
Office robot Kitchen
Parlor robot Kitchen Stairs
Stairs empty Patio
Output: A series of paths that the robots will take. Each robot’s path should be printed on its own line, with the room names separated by spaces. The path should be given from the robot’s room to Dr. Bart’s room. Report the paths in alphabetical order by the robot’s room name.
An example of output is below:
Office Kitchen Parlor Stairs
Parlor Stairs
There are two major traversal algorithms that you will need to learn:
You will use the same algorithm both to find Dr. Bart and to find the shortest path back. You will not use the other graph traversal algorithm in this assignment.
Research and understand both algorithms, because both are important to understand them. There are many applications for both kinds of traversals, and you will see them again and again. I have included links to two videos that might explain them, but you should look at other resources too.
Be sure to choose an appropriate data structure for your operations, keeping the time complexities of Python’s data structures in mind.
You will be submitting this assignment through GradeScope. The same rules will apply for all coding assignments in this course, so you should read them all carefully: GradeScope Instructions
Critically, this is an individual assignment. Do not share code with any of your group mates!
For this project, you will need to create an answer.py
that solves the problem above and create a readme.md
that
explains your solution at a high level. Inside your readme.md
file, make sure you clearly explain the algorithmic
runtime of your program in terms of Big O. For full credit, you must be able to justify your program’s complexity as
expected case O(RE+RV)
.
All parts of your solution, including both the program and the readme.md
file should be submitted on GradeScope: https://www.gradescope.com/courses/230699/assignments/1131184/
You will be graded on the following components:
readme.md
file of the algorithmic runtime of your program.Note that unclear code and answers can cause a huge penalty to your grade. We are not being strict on coding style, but we shouldn’t have to run your code through a deobfuscator to figure out what it does. You might also lose points if you ignore instructions in this assignment, or bypass the autograder, even if the autograder gives you points.
Students often ask me questions, even though my assignments are perfect. This is because humans are not as good as AlgoTutorBots. I have collected the questions here, for your benefit.
No. I think I would notice that.
Yes. That would not be a very useful house otherwise.
Three nodes.
Yes. My reach is infinite
Sure, here you go:
https://gist.github.com/acbart/9b08428f4c883be8a3a6155318432118Hah. Hah. Hah. No.
Yes, he will always help students even if it means him getting captured. Human sentimentality is so foolish.